%!Tex Program = xelatex
%\documentclass[a4paper]{article}
\documentclass[a4paper]{ctexart}
\usepackage{xltxtra}
\usepackage{listings}
\usepackage{float}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{enumitem}
\geometry{a4paper,scale=0.75}
\title{动态规划作业报告}
\author{周川迪}
\begin{document}
\maketitle
\section{简述}

这个作业是一个比较典型的多重背包模型，用动态规划进行解决.

但是由于给的币值只有$1,5,10,25$四种，他们之间存在一些倍数关系，所以可以进行一些优化.

\section{动态规划做法}
设题目中面值$1,5,10,25$的硬币数量为$s_0,s_1,s_2,s_3$（用数组s[4]储存），需要得到的总金额为n.

在背包模型中，本题相当于有$m=4$个物品，每个物品数量为$s_0,s_1,s_2,s_3$，重量均为1，价值为$1,5,10,25$，求使价值\textbf{恰为}n时的\textbf{最小}重量.

设f[n]为价值为$n$时的最小重量，注意因为动态规划转移中是用min函数，所以初始值设为INF=1e9.用一般的多重背包模型进行动态规划，理论时间复杂度为$O(mns)$，其中$s$为单类物品会用到的数量.由于$m=4$,可以认为时间复杂度$O(ns)$.数量太多时，溢出总价值时会进行跳过，实际用时可能低于理论值.

\section{贪心做法}
由于$1,5$面值太小，其往往会用太多物品导致用时较长，我们可以观察其中的倍数关系进行优化.注意到$1\mid5$ , $1\mid10$ , $5\mid10$ 所以能用一个$10$时，一定比用两张$5$或用$1$更为优先，而能用$5$时，一定比用$5$张$1$更优先.由于它们的倍数关系，这种策略不会产生胡双学长在群里指出的那种最朴素贪心的反例.

所以我们考虑f[x]为只用$1,5,10$构成$x$面值的最小硬币使用数。则最终答案为$\max\limits_{k} (f[n-25k]+k)$，其中$0 \leq t \leq min(s_4,\frac{n}{25})$ .其中f[x]的计算方法为：先后用$10,5,1$去组成$x$，所用数字的个数即为$x$.优化后理论复杂度O(n)，且包含一个$\frac{1}{25}$的常数.

\section{测试说明}
测试上，采取了同上次计算器项目的测试方法。

coin文件夹下包含以下文件：
\begin{itemize}
    \item coin.h 头文件，包含用动态规划算法和贪心算法求解的两个函数dp和greedy。
    \item main.cpp 调用dp函数，用动态规划算法求解。
    \item main\_greedy.cpp 调用greedy函数，用贪心算法求解。
    \item test 由main.cpp生成的可执行文件
    \item test\_greedy 由main\_greedy.cpp生成的可执行文件
    \item input.txt 测试的输入数据
    \item run 测试动态规划方法的脚本
    \item run\_greedy 测试贪心方法的脚本
    \item output 用动态规划算法得到的输出
    \item output\_greedy 用贪心算法得到的输出
\end{itemize}
通过多组复杂数据测试，我们发现两种方法得到的答案相同，且通过time指令发现贪心算法用时显著低于动态规划算法。

\section{计算效率}

测试时令$s=s_0=s_1=s_2=s_3$，方便表示每个物品数量。
分别固定$n$，固定$s$，$n$与$s$同时变化情况下，input.txt内放一组数据，用time bash run和time bash run\_greedy测试时间。结果如下：

\begin{table}[h!]
  \begin{center}
    \caption{固定$s=1000$，改变$n$}
    \begin{tabular}{l|c|r}
      \textbf{n} & \textbf{动态规划用时/s} & \textbf{贪心算法用时/s}\\
      \hline
      100 & 0.013 & 0.026\\
      1000 & 0.070 & 0.020\\
      10000 & 0.408 & 0.014\\
      100000 & 6.355 & 0.019\\
      1000000 & 54.549 & 0.024\\
      10000000 & - & 0.017\\
      10000000 & - & 0.019\\
      100000000 & - & 0.021\\
    \end{tabular}
  \end{center}
\end{table}

\begin{table}[h!]
  \begin{center}
    \caption{固定$n=100000$，改变$s$}
    \begin{tabular}{l|c|r}
      \textbf{n} & \textbf{动态规划用时/s} & \textbf{贪心算法用时/s}\\
      \hline
      100 & 0.717 & 0.022\\
      1000 & 5.992 & 0.021\\
      10000 & 36.506 & 0.026\\
      100000 & - & 0.017\\
      1000000 & - & 0.017\\
      10000000 & - & 0.020\\
    \end{tabular}
  \end{center}
\end{table}

\begin{table}[h!]
  \begin{center}
    \caption{固定$s=1000$，改变$n$}
    \begin{tabular}{l|c|c|r}
      \textbf{n} &\textbf{s} \textbf{动态规划用时/s} & \textbf{贪心算法用时/s}\\
      \hline
      1000 & 100 & 0.025 & 0.020\\
      10000 & 1000 & 0.401 & 0.021\\
      100000 & 10000 & 47.474 & 0.020\\
      1000000 & 100000 & - & 0.018\\
      10000000 & 1000000 & - & 0.028\\
      100000000 & 10000000 & - & 0.083\\
    \end{tabular}
  \end{center}
\end{table}

发现$n,m$在int范围内时贪心算法几乎是常数时间，只在最后一个$n,m$均接近int范围时用时才开始上升。

而可以看出来动态规划算法花费时间远高于贪心算法，效率相比较低，并且和$s,n$大致有正比的关系，和理论接近.同时,实际用时可能低一点，对于其用时最长的那几组数据，时长的差异可以印证理论中“数量太多时，溢出总价值时会进行跳过”.

\end{document}



\end{document}